Теорема о функции Эйлера

Натуральные числа $m$ и $k$ **взаимно просты**, если $\text{НОД}(m, k) = 1$. Количество чисел $i \in [ 1..n]$, взаимно простых с $n$, называется **функцией Эйлера** и обозначается через $\phi(n)$.

Пусть $n = p_1^{r_1} p_2^{r_2} \cdots p_k^{r_k}$ — разложение числа $n$ на простые множители. Тогда $$\phi(n) = n \prod_{i=1}^{k} \left(1 - \frac{1}{p_i}\right)$$

Положим $A = [ 1..n]$, $A_i = \{j \mid j \text{ кратно } p_i\}$. Отсюда следует, что $|A_i| = n/p_i$. Так как все $p_i$ — простые, то $|A_{i_1} \cap \dots \cap A_{i_j}| = n/(p_{i_1} \cdots p_{i_j})$. Применим Принцип включений-исключений в общей форме: $$\phi(n) = n - \sum_{i=1}^{k} \frac{n}{p_i} + \dots + (-1)^j \sum_{i_1 < \dots < i_j} \frac{n}{p_{i_1} \cdots p_{i_j}} + \dots + (-1)^k \frac{n}{p_1 \cdots p_k}$$ С другой стороны, раскрыв скобки в произведении, имеем: $$\prod_{i=1}^{k} \left(1 - \frac{1}{p_i}\right) = 1 - \sum_{i=1}^{k} \frac{1}{p_i} + \dots + (-1)^j \sum_{i_1 < \dots < i_j} \frac{1}{p_{i_1} \cdots p_{i_j}} + \dots + (-1)^k \frac{1}{p_1 \cdots p_k}$$ Вынося $n$ за скобки в выражении для $\phi(n)$, полученном по принципу включений-исключений, и сравнивая с разложением произведения, получаем искомую формулу. $\square$